class Zcsh {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] dp1 = new int[triangle.size()];
        int[] dp2 = new int[triangle.size()];
//        if (triangle == null || triangle.isEmpty() || triangle.get(0).isEmpty()) {
//            return -1;
//        }
        dp1[0] = triangle.get(0).get(0);
        int[] reusltDP = dp1;
        for (int i = 1; i < triangle.size(); i++) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                if (j == 0) {
                    dp2[j] = dp1[j] + triangle.get(i).get(j);
                } else if (j == triangle.get(i).size() - 1) {
                    dp2[j] = triangle.get(i).get(j) + dp1[j - 1];
                } else {
                    dp2[j] = triangle.get(i).get(j) + Math.min(dp1[j], dp1[j - 1]);
                }
            }
            reusltDP = dp2;
            int[] temp = dp1;
            dp1 = dp2;
            dp2 = temp;
        }
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < reusltDP.length; i++) {
            result = Math.min(result, reusltDP[i]);
        }
        return result;
    }                                                                       
}